오토마타 이론

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
- 2.1. 20세기 중반의 발전
- 2.2. 1960년대 이후의 발전
3. 오토마타의 정의
- 3.1. 형식적 정의
- 3.2. 작동 방식
4. 오토마타의 종류
5. 형식 언어와의 관계
- 5.1. 촘스키 위계 (Chomsky Hierarchy)
6. 오토마타의 응용
참조

1. 개요

오토마타 이론은 주어진 입력에 따라 작동하는 수학적 기계인 오토마타의 속성을 연구하는 컴퓨터 과학의 한 분야이다. 20세기 중반 유한 오토마타와 관련하여 개발되었으며, 시스템 이론, 정보 시스템, 튜링 머신 등 다양한 분야에 적용되었다. 오토마타는 유한 상태 기계, 푸시다운 오토마타, 튜링 머신 등 여러 종류가 있으며, 각기 다른 형식 언어를 인식한다. 오토마타 이론은 텍스트 처리, 컴파일러, 하드웨어 설계, 프로그래밍 언어, 인공 생명 등 다양한 분야에 응용되며, 형식 언어와의 관계 및 촘스키 위계와 같은 개념을 통해 오토마타의 능력과 표현력을 분석한다.

더 읽어볼만한 페이지

오토마타 이론 - 유한 상태 기계
유한 상태 기계는 입력에 따라 상태를 바꾸는 추상적인 기계 모델로, 초기 상태, 전이 함수, 종료 상태 등으로 구성되며 결정적/비결정적 유한 오토마타로 나뉘어 다양한 분야에 활용된다.
오토마타 이론 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
형식 언어 - 문자열
문자열은 사람이 읽을 수 있는 텍스트를 저장하고 정보를 전달하거나 받는 데 사용되는 순서가 있는 문자들의 시퀀스로, 다양한 형태의 데이터를 표현하며 유한한 길이를 가지고, 프로그래밍 언어에서 기본 또는 복합 자료형으로 제공되고, 문자 집합과 인코딩 방식에 따라 표현 방식이 달라진다.
형식 언어 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.

오토마타 이론
개요
학문 분야	이론 전산학
연구 대상	추상 기계 오토마타
상세 정보
주요 내용	형식 언어 계산 가능성 이론 계산 복잡도 이론 알고리즘
오토마타 종류	유한 상태 기계 푸시다운 오토마타 선형 유계 오토마타 튜링 기계

2. 역사

추상 오토마타 이론은 20세기 중반 유한 오토마타와 관련하여 개발되었다.^[1] 오토마타 이론은 처음에는 이산 매개변수 시스템의 동작을 연구하는 수학적 시스템 이론의 한 분야로 여겨졌다. 초기 연구는 정보 시스템을 설명하기 위해 추상 대수학을 사용했다는 점에서 이전의 시스템 연구와 달랐다.^[2] 유한 상태 변환기 이론은 서로 다른 연구 공동체에 의해 서로 다른 이름으로 개발되었다.^[3] 튜링 머신의 개념도 이 분야에 포함되었다.

1956년, 클로드 섀넌, W. 로스 애시비, 존 폰 노이만, 마빈 민스키, 에드워드 F. 무어, 스티븐 콜 클리니를 포함한 과학자들의 연구를 모은 ''오토마타 연구''가 출판되면서 오토마타 이론은 비교적 자율적인 학문으로 부상했다.^[4]^[12] 이 책에는 클리니가 정규 언어를 설명한 내용과 섀넌이 튜링 머신 프로그램의 비교적 안정적인 복잡성 척도를 설명한 내용이 포함되었다.^[5] 같은 해, 노엄 촘스키는 오토마타와 형식 문법 사이의 대응 관계인 촘스키 위계를 설명했고,^[6] 로스 애시비는 기본적인 집합론을 사용하여 오토마타와 정보를 설명하는 접근하기 쉬운 교과서인 ''사이버네틱스 입문''을 출판했다.

선형 제한 오토마타에 대한 연구는 마이힐-네로드 정리로 이어졌으며,^[7] 이는 형식 언어가 정규 언어이기 위한 필요충분조건을 제공하고, 해당 언어에 대한 최소 기계의 상태 수를 정확하게 계산한다. 정규 언어에 대한 펌핑 보조 정리 역시 정규성 증명에 유용하며, 마이클 O. 라빈과 다나 스콧에 의해 증명되었으며, 결정적 유한 오토마타와 비결정적 유한 오토마타의 계산적 등가성도 증명되었다.^[8]

1960년대에는 "구조 이론" 또는 "대수적 분해 이론"으로 알려진 일련의 대수적 결과가 나타났으며, 이는 상호 연결을 통해 작은 기계로부터 순차 기계를 구현하는 것을 다루었다.^[9] 모든 유한 오토마타는 범용 게이트 집합을 사용하여 시뮬레이션할 수 있지만, 이를 위해서는 시뮬레이션 회로에 임의의 복잡성을 가진 루프가 포함되어야 한다. 구조 이론은 기계의 "루프가 없는" 구현 가능성을 다룬다.^[12]

계산 복잡성 이론도 1960년대에 형성되었다.^[10]^[11] 1960년대 말까지 오토마타 이론은 "컴퓨터 과학의 순수 수학"으로 간주되었다.^[12]

2. 1. 20세기 중반의 발전

추상 오토마타 이론은 20세기 중반 유한 오토마타와 관련하여 개발되었다.^[1] 오토마타 이론은 처음에는 이산 매개변수 시스템의 동작을 연구하는 수학적 시스템 이론의 한 분야로 여겨졌다. 오토마타 이론의 초기 연구는 정보 시스템을 설명하기 위해 추상 대수학을 사용함으로써, 미분 적분학을 사용하여 물질 시스템을 설명하던 이전의 시스템 연구와는 달랐다.^[2] 유한 상태 변환기 이론은 서로 다른 연구 공동체에 의해 서로 다른 이름으로 개발되었다.^[3] 튜링 머신의 이전 개념도 푸시다운 오토마타와 같은 새로운 형태의 무한 상태 오토마타와 함께 이 분야에 포함되었다.

1956년에는 클로드 섀넌, W. 로스 애시비, 존 폰 노이만, 마빈 민스키, 에드워드 F. 무어, 스티븐 콜 클리니를 포함한 과학자들의 연구를 모은 ''오토마타 연구''가 출판되었다.^[4] 이 책의 출판과 함께 "오토마타 이론은 비교적 자율적인 학문으로 부상했다".^[12] 이 책에는 클리니가 정규 언어를 설명한 내용과 섀넌이 튜링 머신 프로그램의 비교적 안정적인 복잡성 척도를 설명한 내용이 포함되었다.^[5] 같은 해, 노엄 촘스키는 오토마타와 형식 문법 사이의 대응 관계인 촘스키 위계를 설명했고,^[6] 로스 애시비는 기본적인 집합론을 사용하여 오토마타와 정보를 설명하는 접근하기 쉬운 교과서인 ''사이버네틱스 입문''을 출판했다.

선형 제한 오토마타에 대한 연구는 마이힐-네로드 정리로 이어졌으며,^[7] 이는 형식 언어가 정규 언어이기 위한 필요충분조건을 제공하고, 해당 언어에 대한 최소 기계의 상태 수를 정확하게 계산한다. 정규 언어에 대한 펌핑 보조 정리 역시 정규성 증명에 유용하며, 마이클 O. 라빈과 다나 스콧에 의해 증명되었으며, 결정적 유한 오토마타와 비결정적 유한 오토마타의 계산적 등가성도 증명되었다.^[8]

1960년대에는 "구조 이론" 또는 "대수적 분해 이론"으로 알려진 일련의 대수적 결과가 나타났으며, 이는 상호 연결을 통해 작은 기계로부터 순차 기계를 구현하는 것을 다루었다.^[9] 모든 유한 오토마타는 범용 게이트 집합을 사용하여 시뮬레이션할 수 있지만, 이를 위해서는 시뮬레이션 회로에 임의의 복잡성을 가진 루프가 포함되어야 한다. 구조 이론은 기계의 "루프가 없는" 구현 가능성을 다룬다.^[12]

계산 복잡성 이론도 1960년대에 형성되었다.^[10]^[11] 1960년대 말까지 오토마타 이론은 "컴퓨터 과학의 순수 수학"으로 간주되었다.^[12]

2. 2. 1960년대 이후의 발전

1960년대에는 "구조 이론" 또는 "대수적 분해 이론"으로 알려진 일련의 대수적 결과가 나타났는데, 이는 상호 연결을 통해 작은 기계로부터 순차 기계를 구현하는 것을 다루었다.^[9] 모든 유한 오토마타는 범용 게이트 집합을 사용하여 시뮬레이션할 수 있지만, 이를 위해서는 시뮬레이션 회로에 임의의 복잡성을 가진 루프가 포함되어야 한다. 구조 이론은 기계의 "루프가 없는" 구현 가능성을 다룬다.^[12]

계산 복잡도 이론도 1960년대에 형성되었다.^[10]^[11] 1960년대 말까지 오토마타 이론은 "컴퓨터 과학의 순수 수학"으로 간주되었다.^[12]

3. 오토마타의 정의

오토마타는 이산적인 시간 동안 주어진 입력에 의존해 작동하는 수학적인 기계이다. 기계는 일정 주기마다 기호 또는 문자를 입력으로 받는데, 이 문자는 정해진 알파벳 집합의 원소여야 한다. 기계가 입력받는 일련의 기호와 문자를 문자열이라고 한다.^[12]

오토마타는 유한한 상태 집합을 가지며, 입력에 따라 현재 상태에서 정해진 다음 상태로 전이한다. 현재 상태와 입력, 다음 상태는 함수 또는 관계로 주어지는데, 이를 전이 함수 또는 전이 관계라고 한다. 기계는 입력의 끝을 만나거나 특정 상태에 있을 때 정지할 수 있으며, 정지했을 때 문자열을 수용하거나 거부한다.^[12]

오토마톤은 개별적인 '시간 단계'로 된 입력 시퀀스가 주어지면 '실행'된다. 오토마톤은 입력 알파벳의 '기호' 또는 '문자' 집합에서 선택된 하나의 입력을 처리한다. 오토마톤이 임의의 단계에서 입력으로 받는 기호는 '단어'라고 하는 기호 시퀀스이다. 오토마톤은 일련의 '상태'를 가지며 실행되는 동안 각 순간에 해당 상태 중 하나에 있다. 오토마톤이 새로운 입력을 받으면 이전 상태와 현재 입력 기호를 매개변수로 사용하는 '전이 함수'에 따라 다른 상태로 이동한다. 동시에 '출력 함수'는 이전 상태와 현재 입력 기호에 따라 '출력 알파벳'에서 기호를 생성한다. 오토마톤은 입력 단어의 기호를 읽고, 단어가 완전히 읽힐 때까지 상태 간을 전이하며, 단어가 유한하면 오토마톤은 '정지'한다. 오토마톤이 정지하는 상태를 '최종 상태'라고 한다.^[12]

형식 언어 이론을 사용하여 오토마톤의 가능한 상태, 입력, 출력 시퀀스를 조사하기 위해 기계는 '시작 상태'와 '수락 상태' 집합을 할당받을 수 있다. 시작 상태에서 시작하는 실행이 수락 상태로 끝나는지에 따라 오토마톤이 입력 시퀀스를 '수락'하거나 '거부'한다고 말할 수 있다. 오토마톤이 수락하는 모든 단어의 집합은 '오토마톤이 인식하는 언어'라고 한다.

3. 1. 형식적 정의

오토마타는 다음 요소들로 구성된 튜플(n-tuple)

M = \langle \Sigma, \Gamma, Q, \delta, \lambda \rangle

로 표현될 수 있다.^[1]

요소	설명
$\Sigma$	오토마타의 입력 알파벳. 유한한 기호 집합이다.
$\Gamma$	오토마타의 출력 알파벳. 유한한 기호 집합이다.
$Q$	상태 집합.
$\delta$	다음 상태 함수 또는 전이 함수. $\delta: Q \times \Sigma \to Q$ 로 표현되며, 상태-입력 쌍을 후속 상태에 매핑한다.
$\lambda$	다음 출력 함수. $\lambda: Q \times \Sigma \to \Gamma$ 로 표현되며, 상태-입력 쌍을 출력에 매핑한다.

만약 $Q$ 가 유한하다면, $M$ 은 유한 오토마타가 된다.^[1]

오토마타는 입력 알파벳( $\Sigma$ )에 속하는 기호들로 이루어진 유한한 문자열 $a_1a_2...a_n$ 을 읽는다. 이를 입력 단어라고 하며, 모든 단어의 집합은 $\Sigma^*$ 로 표시한다.^[1]

오토마타의 실행은 상태 시퀀스 $q_0, q_1, ..., q_n$ ( $q_i \in Q$ )으로 표현된다. $0 < i \le n$ 에 대해 $q_i = \delta(q_{i-1}, a_i)$ 가 성립하며, 시작 상태 $q_0$ 에서 입력 $a_1a_2...a_n \in \Sigma^*$ 를 받아 실행된다. 오토마타는 전이 함수 $\delta(q_{i-1}, a_i)$ 에 따라 다음 상태 $q_i$ 를 선택하고, 마지막 기호 $a_n$ 을 읽으면 최종 상태 $q_n$ 에 도달한다. 각 단계에서 출력 함수 $\lambda(q_{i-1}, a_i)$ 에 따라 출력 기호가 생성된다.^[1]

전이 함수 $\delta$ 는 $\overline\delta: Q \times \Sigma^* \to Q$ 로 확장될 수 있다. 빈 문자열 $\varepsilon$ 에 대해 $\overline\delta(q, \varepsilon) = q$ 이며, 문자열 $wa$ ( $a$ 는 마지막 기호, $w$ 는 나머지 문자열)에 대해 $\overline\delta(q, wa) = \delta(\overline\delta(q, w), a)$ 이다. 출력 함수 $\lambda$ 도 $\overline\lambda(q, w)$ 로 확장되어, 상태 $q$ 에서 단어 $w$ 실행 시 전체 출력을 나타낸다.^[1]

오토마타를 형식 언어 이론에서 연구할 때는 수용기로 간주한다. 출력 알파벳과 함수 $\Gamma$ , $\lambda$ 대신 다음을 사용한다.^[1]

$q_0 \in Q$ : 지정된 시작 상태
$F \subseteq Q$ : 수용 상태 집합

단어

w = a_1a_2...a_n \in \Sigma^*

가

\overline\delta(q_0, w) \in F

를 만족하면 (전체 문자열

w

를 읽은 후 기계가 수용 상태에 도달하면) 오토마타에 대한 수용 단어가 된다.^[1]

오토마타에 의해 인식되는 언어

L \subseteq \Sigma^*

는 오토마타가 수용하는 모든 단어의 집합, 즉

L = \{w \in \Sigma^* \ |\ \overline\delta(q_0, w) \in F\}

이다.^[1]

인식 가능한 언어는 특정 오토마타에 의해 인식되는 언어의 집합이다. 유한 오토마타의 경우 인식 가능한 언어는 정규 언어이다. 오토마타의 종류에 따라 인식 가능한 언어가 달라진다.^[1]

3. 2. 작동 방식

오토마타는 이산적인 시간 단계에 따라 작동하는 수학적 기계이다. 각 단계마다 기계는 정해진 알파벳 집합의 원소인 기호 또는 문자를 입력으로 받는다. 입력되는 기호들의 연속된 순서를 문자열이라고 한다. 오토마타는 유한한 상태 집합을 가지며, 현재 상태와 입력 기호에 따라 전이 함수(또는 전이 관계)에 의해 결정되는 다음 상태로 이동한다.

오토마타의 작동은 입력 문자열, 출력 문자열(선택 사항), 기억 장소(선택 사항)에 따라 형상 (계산) 간의 전이로 나타낼 수 있다.

w: 문자열. 가능한 모든 문자열의 원소이다.
w ∈ Σ* 이고, |w| = n일 때 w = s₀s₁s₂...s_n-1
여기서 Σ*는 알파벳의 클레이니 스타이다.
L: 언어. 집합 L⊆Σ*에 대해, 기계 M이 수용하는 모든 문자열 w에 대해서만 w∈L일 때 L은 M이 인지하는 언어이다.
여기서 L은 인지 가능한 형식 언어이다.
q₀w = q₀s₀...s_n-1: 초기 형상(q₀ = S). 일반적으로 입력 문자열은 초기 상태의 기계가 다음 단계에서 읽을 수 있도록 대기한다.
w'q_f = q₀s₀'...s_m-1'q_f: 최종 형상(q_f ∈ F)의 예시.

오토마톤은 개별적인 '시간 단계'로 된 입력 시퀀스에 따라 '실행'된다. 입력 알파벳의 기호를 처리하며, 입력으로 받는 기호들의 시퀀스를 '단어'라고 한다. 오토마톤은 여러 '상태'를 가지며, 실행 중에는 항상 그 중 한 상태에 있다. 새로운 입력을 받으면, 이전 상태와 현재 입력 기호를 매개변수로 하는 '전이 함수'에 따라 다른 상태로 '전이'한다. 동시에 '출력 함수'는 이전 상태와 현재 입력 기호에 따라 '출력 알파벳'에서 기호를 생성한다. 입력 단어의 기호를 모두 읽으면 오토마톤은 '정지'하고, 정지하는 상태를 '최종 상태'라고 한다.

형식 언어 이론에서는 오토마톤의 가능한 상태, 입력, 출력 시퀀스를 연구하기 위해 '시작 상태'와 '수락 상태' 집합을 설정한다. 시작 상태에서 시작하여 수락 상태로 끝나는 실행에 따라 오토마톤이 입력 시퀀스를 '수락'하거나 '거부'한다고 판단한다. 오토마톤이 수락하는 모든 단어의 집합을 '오토마톤이 인식하는 언어'라고 하며, 전자 잠금 장치가 그 예시이다.

오토마타는 형식적으로 튜플^[12]로 표현할 수 있다.

$\Sigma$ : 입력 알파벳 (유한한 기호 집합)
$\Gamma$ : 출력 알파벳 (유한한 기호 집합)
$Q$ : 상태 집합
$\delta$ : 다음 상태 함수 또는 전이 함수 ( $\delta : Q \times \Sigma \to Q$ )
$\lambda$ : 다음 출력 함수 ( $\lambda : Q \times \Sigma \to \Gamma$ )

Q

가 유한하면,

M

은 유한 오토마타이다.

오토마타는 입력 단어 (

a_1a_2...a_n

,

a_i \in \Sigma

)를 읽고, 모든 단어의 집합은

\Sigma^*

로 표시된다.

상태 시퀀스

q_0,q_1,...,q_n

(

q_i \in Q

이고

0 < i \le n

에 대해

q_i = \delta(q_{i-1}, a_i)

)은 상태

q_0

에서 시작하는 입력

a_1a_2...a_n \in \Sigma^*

에 대한 오토마타의 실행이다. 오토마타는 시작 상태

q_0

에서 입력

a_1

을 받고, 전이 함수

\delta(q_{i-1},a_i)

에 따라 다음 상태

q_i

를 선택하여 최종 상태

q_n

에 도달한다. 각 단계에서 출력 함수

\lambda(q_{i-1},a_i)

에 따라 출력 기호를 생성한다.

전이 함수

\delta

는

\overline\delta: Q \times \Sigma^* \to Q

로 확장된다. 빈 문자열

\varepsilon

에 대해

\overline\delta(q, \varepsilon) = q

이고, 문자열

wa

에 대해

\overline\delta(q, wa) = \delta(\overline\delta(q,w),a)

이다. 출력 함수

\lambda

도

\overline\lambda(q,w)

로 확장되어 상태

q

에서 단어

w

실행 시 기계의 전체 출력을 나타낸다.

오토마타를 형식 언어 이론에서 연구할 때는 수용기로 간주하며, 출력 알파벳과 함수 대신 다음을 사용한다.

$q_0 \in Q$ : 시작 상태
$F$ : 수용 상태 집합 ( $F \subseteq Q$ )

단어

w = a_1a_2...a_n \in \Sigma^*

가

\overline\delta(q_0,w) \in F

이면 (전체 문자열

w

소모 후 수용 상태), 오토마타에 대한 수용 단어이다.

오토마타가 인식하는 언어

L \subseteq \Sigma^*

는 수용되는 모든 단어의 집합, 즉

L = \{w \in \Sigma^* \ |\  \overline\delta(q_0,w) \in F\}

이다.

인식 가능한 언어는 일부 오토마타에 의해 인식되는 언어의 집합이다. 유한 오토마타의 경우 인식 가능한 언어는 정규 언어이며, 오토마타 종류에 따라 인식 가능한 언어가 달라진다.

4. 오토마타의 종류

다음은 오토마타 종류의 불완전한 목록이다.

오토마톤	인식 가능한 언어
비결정적/결정적 유한 상태 기계 (FSM)	정규 언어
결정적 푸시다운 오토마톤 (DPDA)	결정적 문맥 자유 언어
푸시다운 오토마톤 (PDA)	문맥 자유 언어
선형 경계 오토마톤 (LBA)	문맥 민감 언어
튜링 기계	재귀적 가산 언어
결정적 뷔치 오토마톤	ω-극한 언어
비결정적 뷔치 오토마톤	오메가 정규 언어
라빈 오토마톤, 스트리트 오토마톤, 패리티 오토마톤, 뮬러 오토마톤	오메가 정규 언어
가중 오토마톤

다음은 다양한 종류의 가상 머신의 능력 측면에서 불완전한 계층 구조이다. 이 계층 구조는 머신이 허용할 수 있는 언어의 중첩된 범주를 반영한다.^[14]

오토마톤
결정적 유한 오토마톤 (DFA) -- 가장 낮은 능력 (동일한 능력)	(동일한 능력) 비결정적 유한 오토마톤 (NFA)
(위는 약함) $\cap$ (아래는 강함)
결정적 푸시다운 오토마톤 (DPDA-I) 1개의 푸시다운 저장소 포함
$\cap$
비결정적 푸시다운 오토마톤 (NPDA-I) 1개의 푸시다운 저장소 포함
$\cap$
선형 경계 오토마톤 (LBA)
$\cap$
결정적 푸시다운 오토마톤 (DPDA-II) 2개의 푸시다운 저장소 포함	비결정적 푸시다운 오토마톤 (NPDA-II) 2개의 푸시다운 저장소 포함	결정적 튜링 기계 (DTM)	비결정적 튜링 기계 (NTM)	확률적 튜링 기계 (PTM)	다중 테이프 튜링 기계 (MTM)	다차원 튜링 기계

헤지 오토마타

; 광의의 오토마타:

4. 1. 유한 오토마타 (Finite Automata)

결정적 유한 오토마타 (Deterministic Finite Automaton, DFA)
비결정적 유한 오토마타 (Nondeterministic Finite Automaton, NFA)
ε-전이를 포함하는 비결정적 유한 오토마타 (Nondeterministic Finite Automaton, with ε transitions (FND-ε, ε-NFA))

4. 2. 푸시다운 오토마타 (Pushdown Automata, PDA)

유한 오토마타와 달리, 푸시다운 오토마타(Pushdown Automaton, PDA)는 스택을 사용하여 문맥 자유 문법을 처리할 수 있다.

4. 3. 선형 제한 오토마타 (Linear Bounded Automata, LBA)

선형 제한 오토마타 (Linear Bounded Automaton, LBA)

4. 4. 튜링 머신 (Turing Machine)

튜링 머신 (Turing Machine)
* 결정적 튜링 머신 (Deterministic Turing Machine, DTM)
* 비결정적 튜링 머신 (Nondeterministic Turing Machine, NTM)

5. 형식 언어와의 관계

오토마타는 형식 언어 이론에서 "수용기"로 간주될 수 있다. 이때 출력 알파벳과 함수 $\Gamma$ 및 $\lambda$ 는 다음과 같이 대체된다.

$q_0 \in Q$ : 지정된 ''시작 상태''
$F \subseteq Q$ : ''수용 상태''라고 불리는 $Q$ 의 상태 집합

이를 통해 ''수용 단어''와 ''인식된 언어''를 정의할 수 있다.

수용 단어: 단어 $w = a_1a_2...a_n \in \Sigma^*$ 가 $\overline\delta(q_0,w) \in F$ 이면, 즉 전체 문자열 $w$ 를 소모한 후 기계가 수용 상태에 있다면, 이 단어는 오토마타에 대한 ''수용 단어''이다.
인식된 언어: 오토마타에 의해 ''인식''되는 언어 $L \subseteq \Sigma^*$ 는 오토마타에 의해 수용되는 모든 단어의 집합, 즉 $L = \{w \in \Sigma^* \ |\ \overline\delta(q_0,w) \in F\}$ 이다.

인식 가능한 언어는 일부 오토마타에 의해 인식되는 언어의 집합이다. 유한 오토마타의 경우 인식 가능한 언어는 정규 언어이다. 오토마타의 종류에 따라 인식 가능한 언어는 다르다.

5. 1. 촘스키 위계 (Chomsky Hierarchy)

어떤 언어(특히 형식 언어)의 문법(형식 문법)과 그것을 생성하는 생성 규칙, 그리고 그것을 수용하는 오토마톤 사이에는 대응 관계가 있으며, 또한 언어(형식 언어)를 집합으로 했을 때 부분 집합이 된다는 관계가 계층을 이루고 있다는 사실이 있다. 자세한 내용은 형식 언어의 계층 문서 및 촘스키 계층 문서를 참조하라.

6. 오토마타의 응용

오토마타 이론의 각 모델은 여러 응용 분야에서 중요한 역할을 한다. 유한 오토마타는 텍스트 처리, 컴파일러 및 하드웨어 설계에 사용된다. 문맥 자유 문법(CFG)은 프로그래밍 언어 명세 및 인공 지능에 사용된다. 원래 CFG는 자연어 연구에 사용되었다. 셀룰러 오토마타는 인공 생명 분야에서 사용되며, 가장 유명한 예는 존 콘웨이의 라이프 게임이다. 생물학에서 오토마타 이론을 사용하여 설명할 수 있는 다른 예로는 연체 동물과 솔방울 성장, 색소 침착 패턴 등이 있다. 더 나아가, 어떤 종류의 이산 오토마톤에 의해 전체 우주가 계산된다는 이론을 일부 과학자들이 옹호하고 있다. 이 아이디어는 콘라트 추제의 연구에서 시작되었으며, 에드워드 프레드킨에 의해 미국에서 대중화되었다. 오토마타는 유한체 이론에도 나타난다. 차수 2 다항식의 구성으로 작성할 수 있는 기약 다항식 집합은 실제로 정규 언어이다.^[15] 오토마타를 사용할 수 있는 또 다른 문제는 정규 언어의 유도이다.

참조

_[1] 웹사이트 The Structures of Computation and the Mathematical Structure of Nature http://www.rutherfor[...] The Rutherford Journal 2020-06-07
_[2] 서적 Sequential Machines and Automata Theory John Wiley & Sons 1967
_[3] 논문 The Place of the Brain in the Natural World http://www.rossashby[...] 2021-03-29
_[4] 서적 Automata Studies Princeton University Press 1956
_[5] 서적 An Introduction to Kolmogorov Complexity and its Applications Springer-Verlag 1997
_[6] 논문 Three models for the description of language https://chomsky.info[...] 1956
_[7] 논문 Linear Automaton Transformations https://www.ams.org/[...] 1958
_[8] 논문 Finite Automata and Their Decision Problems http://www.cse.chalm[...] 1959-04
_[9] 서적 Algebraic Structure Theory of Sequential Machines Prentice-Hall 1966
_[10] 웹사이트 Computational complexity of recursive sequences http://www.cs.albany[...] 1964
_[11] 웹사이트 A Short History of Computational Complexity https://people.cs.uc[...] 2002
_[12] 서적 Theories of Abstract Automata Prentice-Hall 1969
_[13] arXiv Automata, languages, and grammars 2019-07-31
_[14] 서적 An Introduction to Formal Languages and Machine Computation https://books.google[...] World Scientific Publishing Co. Pte. Ltd.
_[15] 간행물 Irreducible compositions of degree two polynomials over finite fields have regular structure Oxford University Press
_[16] 논문 Fifty Years of Automata Simulation: A Review http://dl.acm.org/ci[...]
_[17] 문서 Jiří Adámek and [[Věra Trnková]]. 1990. ''Automata and Algebras in Categories''. Kluwer Academic Publishers:Dordrecht and Prague
_[18] 서적 Categories for the Working Mathematician Springer 1971
_[19] 웹사이트 James Worthington.2010.Determinizing, Forgetting, and Automata in Monoidal Categories. ASL North American Annual Meeting, 17 March 2010 http://www.math.corn[...]
_[20] 문서 Aguiar, M. and Mahajan, S.2010. ''"Monoidal Functors, Species, and Hopf Algebras"''
_[21] 문서 Meseguer, J., Montanari, U.: 1990 Petri nets are monoids. ''Information and Computation'' '''88''':105–155

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com